import java.util.*;

/**
 * 501. 二叉搜索树中的众数
 */
public class No501 {
    ArrayList<Integer> resList = new ArrayList<>();
    int maxTimes = 0;

    public int[] findMode(TreeNode root) {
        List<Integer> list = mid(root);
        HashMap<Integer, Integer> hashSet = new HashMap<>();
        for (Integer i : list) {
            if (hashSet.containsKey(i)) {
                hashSet.put(i, hashSet.get(i) + 1);
            } else {
                hashSet.put(i, 1);
            }
        }
        hashSet.forEach((key, value) -> maxTimes = Math.max(maxTimes, value));
        hashSet.forEach((key, value) -> {
            if (value == maxTimes) {
                resList.add(key);
            }
        });
        int[] ints = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            ints[i] = resList.get(i);
        }
        return ints;
    }

    public List<Integer> mid(TreeNode node) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        if (node == null) {
            return arrayList;
        }
        arrayList.addAll(mid(node.left));
        arrayList.add(node.val);
        arrayList.addAll(mid(node.right));
        return arrayList;
    }
}
